In modern computers, data bytes are typically stored in memory as a binary data field, consisting of 1's and 0's. In particular, decimal numbers are represented and stored as a binary number field.
TABLE 1 below illustrates the representation of decimal numbers 0 to 10 in binary form.
______________________________________ DECIMAL BINARY ______________________________________ 0 0 1 1 2 10 3 11 4 100 5 101 6 110 7 111 8 1000 9 1001 10 1010 ______________________________________
For example, decimal number "5" is equal to: EQU 1.times.2.sup.2 +0.times.2.sup.1 +1.times.2.sup.0
which is represented as "101". Moreover, decimal number "10" is equal to: EQU 1.times.2.sup.3 +0.times.2.sup.2 +1.times.2.sup.1 +0.times.2.sup.0
which is represented as "1010".
Binary numbers are typically formatted as floating point numbers. For example, the binary number "101" (decimal number "5") can be represented in floating point binary notation as either EQU 1.01.times.2.sup.2 (A) or EQU 0.101.times.2.sup.3 (B)
depending on the desired convention, that is, whether the most significant "1" is to be positioned to the left or right of the decimal point. The actual binary digits "101" are known as the mantissa of the floating point number, while the value 2.sup.n is the exponent. The value of the exponent represents the number of places that the binary number occupies to the right of the decimal point.
Hence, to determine the value of floating point binary number "1.01.times.2.sup.2", one would simply determine the value of the mantissa without the decimal point (e.g. determine the value of binary number "101", which is equal to decimal number "5"). Likewise, the value of floating point binary number "0.101.times.2.sup.3 " is determined in the same manner. In other words, the decimal point is viewed as being moved to the right the number of places indicated by the exponent (i.e. 3) to arrive at the binary number "101".
A floating point binary number is known as "normal" when the most significant bit of its mantissa is a "1", and is "denormal" when the most significant bit of its mantissa is "0". Hence, both of the floating point numbers (A) and (B) represented above are "normal".
For consistency, it is desirable to represent all floating point binary numbers in their "normal" form, regardless of their size. This is especially true in computers. In that regard, using format (B) above, the decimal numbers "1", "5" and "10" can be represented as normal floating point numbers 0.1.times.2.sup.1, 0.101.times.2.sup.3, and 0.1010.times.2.sup.4, respectively.
However, in order to perform certain arithmetic operations of two floating point binary numbers, it is necessary that the exponents of both numbers are the same. For example, if one wishes to subtract "0.101.times.2.sup.3 " (decimal number "5") from "0.1010.times.2.sup.4 " (decimal number "10"), it is necessary to "denormalize" the number "0.101.times.2.sup.3 ", so that it is represented as "0.0101.times.2.sup.4 ". Thus, both numbers now having the exponent "2.sup.4 " can be subtracted to give the result "0.0101.times.2.sup.4 " (decimal number "5"). Accordingly, so that this number is stored or recorded in a manner consistent with the other floating point numbers, it is desirable to "normalize" this number to "0.101.times.2.sup.3 ".
Such normalization is accomplished by shifting the binary data string a given number of bit positions to the left until the leading "1" is in the most significant bit position. Concurrently, a number representing the number of shifts to the left is subtracted from the exponent. In this example, the mantissa is shifted to the left by one bit, and accordingly, the exponent is decremented by 1.
Hence, to normalize a denormalized number, it is necessary to determine where the most significant "1" is located in the mantissa, or rather, the number of leading zeros before that most significant "1". Therefore, a computer capable of performing binary arithmetic operations must include a circuit capable of locating the leading "1" in a binary data field. It addition, it is also desirable that the circuit determine whether zeros are stored in all of the data bits of the binary data field, which indicates that the binary floating point number is "0" and that no normalization need be performed.
A conventional circuit for normalizing a binary data field is described in U.S. Pat. No. 4,586,154 to Berry. In the Berry circuit, an 8-bit fixed-size read-only memory U1 receives the "top" eight data bits of a 16-bit binary data word, while another 8-bit fixed-size read-only memory U2 receives the "bottom" eight data bits of the 16-bit binary data word.
The memories U1 and U2 analyze the top eight and bottom eight data bits, respectively, to determine the number of shifts required for normalization. If the memory U1 determines that the top eight bits are all "0" (or all "1" if the number is a negative number represented in two's complement format), or that more than seven shifts are required, the memory U1 outputs a signal (i.e. "1") at output O.sub.5 to a quad 2:1 multiplexor U3. This signal indicates that the multiplexor U3 is to consider the binary data, representing the number of shifts required, that is being output from memory U2.
Conversely, if memory U1 determines that less than seven shifts are required, the memory U1 outputs a signal (i.e. "0") at output O.sub.5 to the quad 2:1 multiplexor U3. This signal indicates that the multiplexor U3 is to consider the binary data, representing the number of shifts required, that is being output from memory U1.
Based the signal output at O.sub.5 of memory U1, the multiplexor considers the binary data representing the number of shifts required that is provided by either U1 or U2, and controls the parallel shift network, comprising 4-bit parallel shifters U4-U11, to effect the shifting accordingly. In addition, if the binary data output from U2 is to be used, and indicates that all of the bottom eight bits are "0", then the entire 16-bit number is recognized as "0", and no shifting will occur.
The Berry circuit, however, has limited applications. For example, since the circuit is similar to a programmable logic array (PLA), it is not readily adaptable in data flow circuitry. Hence, for practical purposes, the circuit cannot be used effectively in conjunction with devices requiring high-speed data flow.
Another example of a conventional normalization circuit is described in U.S. Pat. No. 4,785,421 to Takahashi et al. In the Takahashi circuit, data from all 16-bits of a 16-bit data register are provided to a leading "1" detector circuit. The leading "1" detector circuit outputs 16 bits of data to an encoder, which in turn outputs a binary number representing the position of the leading "1" in the 16-bit data field.
Because the leading "1" detector of the Takahashi circuit comprises a large number of passgates in series (i.e. 16 passgates), the operation of the circuit is very slow by today's computer standards. Accordingly, the Takahashi circuit is not readily adaptable for high speed computers.
A third example of a conventional normalization circuit is described in U.S. Pat. No. 5,241,490 to Poon. The Poon circuit operates to normalize a 69-bit mantissa of a floating point number. To perform this function, eight 8-input OR gates are coupled in parallel so that each receives a different group of eight consecutive bits of data from the 69-bit field, while a single 5-input OR gate is coupled in parallel with the OR gates to receive a group of five consecutive data bits from the 69-bit field. In this arrangement, the five bit group includes the five least significant bits in the 69-bit field.
Each of the OR gates provides an output "0" when all of its inputs are "0", that is when all of the bits in the group of bits that it is receiving are "0", and provides an output "1" when any of its inputs are "1". Hence, the outputs of the OR gates act as a zero-detect for each bit group.
The 69-bit data field is also input to a multiplexor unit 109 which comprises nine byte selectors. Each of the byte selectors, except one, receives a different one of the eight 8-bit data groups described above, while that one remaining byte selector receives the single 5-bit data group. Hence, the nine byte selectors correspond to the eight 8-input OR gates and one 5-input OR gate.
The outputs of the OR gates, described above, are provided to a 9-bit input prioritizer circuit 105 such that the output from the OR gate which receives the 8-bit group of bits 69-62 (the most significant eight bits) of the 69-bit data field is the most significant bit of the 9-bit input, the output from the OR gate which receives the 8-bit group of bits 61-54 is the next significant bit, and so on. The output from the 5-input OR gate which receives bits 4-0 of the 69-bit data field is thus the least significant bit of the 9-bit input.
The prioritizer circuit recognizes which of the input bits are "1" and provides a 9-bit binary output signal having a "1" in the bit location corresponding to the most significant input that is "1". In other words, if the binary input to the nine input terminals of the prioritizer circuit is "001001010", with the leftmost bit being the most significant bit, the prioritizer circuit provides a binary output signal "001000000".
Each bit of the 9-bit output signal from the prioritizer circuit is input to one of the corresponding inputs A0-A8, respectively, of each of the byte selectors in the multiplexor unit 109. Hence, the byte selector receiving the "1" in the 9-bit output signal outputs the group of bits that it receives, which is the most significant group of bits containing at least one "1". Conversely, the byte selectors receiving the 0's in the 9-bit output from the prioritizer circuit will output 0's.
The outputs from all the byte selectors are OR'ed by OR gate 155 and thus, the multiplexor outputs a binary signal equal to the most significant bit group of the 69-bit field having at least one "1". This output signal from the multiplexor is input to a prioritizer circuit 111, which operates similar to the prioritizer circuit 105 described above. Accordingly, the signals output by both prioritizer circuits are used to shift the 69-bit data field by the appropriate number of bits.
However, the Poon circuit never outputs a single binary number representing the amount of leading zeros that are present in the 69-bit data field. That is, the circuit merely outputs two shift control signals which cause barrel shifters to shift the 69-bit data field a designated number of bits to the left. In particular, one of the control signals causes a barrel shifter to shift the 69-bit data field to the left in 8-bit increments to reach a designated 8-bit group containing the leading "1". Then, the second control signal is used to shift the data field bit-by-bit so that the leading "1" becomes the most significant bit.
The examples of conventional normalization circuits described above, illustrate that such circuits are often slow or occupy much chip real estate due to their complexity. In particular, the circuits which determine the amount of leading zeros in the binary data filed are often impractical due to their size or inability to provide high speed data flow. Therefore, a simplified normalization circuit having a high speed circuit for determining the amount of the leading ones or zeros in an data field, while also indicating if the data in the field is zero, is highly desirable.